// 算法复杂度
O(1)
const increment = n => n++
// 不管n如何增长，都不会影响到这个函数的计算时间，因此这个代码的时间复杂度都是O(1)
O(n)
const linearSearch = (arr, target) => {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i
        }
    }
    return -1
}
// 线性查找的时间消化与输入的数组数量n成一个线性比例，随着n规模的增大，时间也会线性增长
O(logn)
// 对数复杂度，随着问题规模n的增长，计算时间也会随着n对数级增长。 典型的例子是二分查找法
function binarySearch(arr, target) {
	let max = arr.length - 1
	let min = 0
	while (min <= max) {
		let mid = Math.floor((max + min) / 2)
		if (target < arr[mid]) {
			max = mid - 1
		} else if (target > arr[mid]) {
			min = mid + 1
		} else {
			return mid
		}
	}
	return -1
}
// 在二分查找法的代码中，通过while循环，成 2 倍数的缩减搜索范围，也就是说需要经过 log2^n 次即可跳出循环。
// 事实上在实际项目中，O(logn)是一个非常好的时间复杂度，比如当n=100的数据规模时，二分查找只需要7次，线性查找需要100次，这对于计算机而言差距不大，
// 但是当有10亿的数据规模的时候，二分查找依然只需要30次，而线性查找需要惊人的10亿次，O(logn)时间复杂度的算法随着数据规模的增大，它的优势就越明显。
O(nlogn)
// 线性对数复杂度，随着数据规模n的增长，计算时间也会随着n呈线性对数级增长。 这其中典型代表就是归并排序
const mergeSort = array => {
	const len = array.length
	if (len < 2) {
		return len
	}

	const mid = Math.floor(len / 2)
	const first = array.slice(0, mid)
	const last = array.slice(mid)

	return merge(mergeSort(fist), mergeSort(last))

	function merge(left, right) {
		var result = [];
		while (left.length && right.length) {
			if (left[0] <= right[0]) {
				result.push(left.shift());
			} else {
				result.push(right.shift());
			}
		}
	
		while (left.length)
			result.push(left.shift());
	
		while (right.length)
			result.push(right.shift());
		return result;
	}
}
O(n²)
// 平方级复杂度，典型情况是当存在双重循环的时候，即把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了，代表应用是冒泡排序算法
function bubleSort(arra){
	var temp;
	for(var i=0;i<arra.length;i++){
		for(var j=0;j<arra.length-i-1;j++){
			if(arra[j]>arra[j+1]){
				temp=arra[j];
				arra[j]=arra[j+1];
				arra[j+1]=temp;
			}
		}
	};
	return arra;
}